package leetcode;

/**
 * 45. 跳跃游戏 II      https://leetcode.cn/problems/jump-game-ii
 */
public class LeetCode45 {

    public static int jump(int[] nums) {
        int maxPosition = 0;
        int end = 0;
        int ans = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                ans++;
                if(maxPosition >= nums.length - 1) {
                    break;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {5, 6, 4, 4, 6, 9, 4, 4, 7, 4, 4, 8, 2, 6, 8, 1, 5, 9, 6, 5, 2, 7, 9, 7, 9, 6, 9, 4, 1, 6, 8, 8, 4, 4, 2, 0, 3, 8, 5};
        System.out.println(jump(nums));

        int[] nums1 = {2, 3, 0, 1, 4};
        System.out.println(jump(nums1));
    }
}
